package LeetCodeHot100TopInterview;
import java.util.LinkedList;
import java.util.List;

public class Q118_PascalTriangle {

    //杨辉三角
    //生成杨辉三角前 N 行
    public List<List<Integer>> generate(int numRows) {

        if (numRows <= 0){
            return new LinkedList<>();
        }


        //初始化
        List<List<Integer>> ans = new LinkedList<>();
        for (int i = 1; i <= numRows ; i++) {
            List<Integer> tmp = new LinkedList<>();
            for (int j = 0; j < i; j++) {
                tmp.add(1);
            }
            ans.add(tmp);
        }
        //加工
        //迭代就行了
        List<Integer> tmp = null;
        if (ans.size() > 1)
        tmp = ans.get(1);
        for (int i = 2; i < ans.size(); i++) {
            List<Integer> target = ans.get(i);
            //第 2 个到倒数第二个
            for (int j = 1; j < target.size() - 1; j++) {
                target.set(j, tmp.get(j - 1) + tmp.get(j));
            }
            ans.set(i, target);
            tmp = target;
        }

        return ans;
    }

    public static void main(String[] args) {
        Q118_PascalTriangle fun = new Q118_PascalTriangle();
        System.out.println(fun.generate(5));
    }
}
